The present invention relates to a method and an apparatus for transmitting data frames, as well as to a method and an apparatus for data rate matching; in particular, by using a repetition of bits to be transmitted.
Digital communications systems are designed for transmitting data by representing the data in a form that facilitates the transmission of the data via a communication medium. For example, in the case of radio transmissions, the data are transmitted, represented as radio signals, between transmitters and receivers of the communications system. In the case of broadband telecommunications networks, the data can be represented as light transmitted, for example, via a fiber optic network between transmitters and receivers in the system.
During the transmission of data, bits or symbols of the transmitted data can be corrupted, with the effect that these bits or symbols cannot be correctly determined in the receiver. For this reason, the data communications systems frequently have ways to moderate the corruption of the data that occurs during the transmission. One of these ways consists in equipping transmitters in the system with coders that code the data before transmission in accordance with an error control code. The error control code is designed such that it adds redundancy to the data in a controlled fashion. In the receiver, errors that occur during transmission can be corrected by decoding the error control code. As a result, the original data are reproduced. The decoding is effected by using an error decoding algorithm that corresponds to the error control code which is known to the receiver.
After the data have been coded, it is frequently necessary for the purpose of data rate matching to puncture or to repeat data bits or symbols from a block of coded data before these data are transmitted. The term puncturing/repetition is intended here to signify a process of removing or deleting bits from a coded data block with the effect that the punctured bits are not transmitted with this data block, or to signify a process of repeating bits from a coded data block with the effect that the bits to be repeated are transmitted several times with this data block. Even if only one term “puncturing” or “repetition” is commonly used below, it goes without saying that the present invention also can be used for the other case of “repetition” or “puncturing.”
The puncturing could be required, for example, because a multiple access method that serves for transmitting the data via the data-carrying media requires formatting of the data to form blocks of predetermined size, which size does not correspond to the size of the coded data frame.
In order to accommodate the coded data frame in the transport data block of the predetermined size, data bits are therefore either punctured from the coded data frame in order to reduce the size of the coded data block, in a case in which the coded data frame is larger than the size of the transport block, or bits in the coded data frame are repeated, in a case in which the coded data frame is smaller than the predetermined size of the transport block. In a case in which the data frame is smaller than the transport data block, the data bits (bits) or data symbols are repeated to the extent necessary to fill the rest of the transport data block.
Those skilled in the art are familiar with the fact that one effect of puncturing a coded data frame is that the probability of correct reproduction of the original data is reduced. Moreover, the performance of known error control codes and of decoders for these error control codes is best when the errors that occur during the transmission of the data are caused by Gaussian noise, since this has the effect that the errors are distributed independently over the transport data block. When a coded data frame is intended to be punctured, the positions in the coded data frame at which bits are punctured are to be separated as far as possible from one another. To this extent, the puncturing positions should be distributed uniformly over the data frame. Since errors during transmission frequently occur in bursts, particularly in the case of radio communications systems that do not use interleaving, and since the repetitions of bits are not intended to particularly raise the quality only in a certain region of the data frame but as uniformly as possible, bit positions in a coded or uncoded data frame at which data bits are intended to be repeated should also be arranged such that they are uniformly separated from one another in the entire data frame.
Known methods for selecting the positions of bits or symbols that are intended to be punctured or repeated in a coded data frame include the division of the number of bits or symbols in a frame by the number of bits or symbols that are intended to be punctured or repeated, and the selection of the bit positions with integral values corresponding to the division. However, in a case in which the number of bits to be punctured is not an integral division of the number of bits in the data frame, this does not lead to a uniform spacing of the punctured or repeated bit positions, thus resulting in the disadvantage that specific bit positions are situated closer to one another than this whole number or are situated further (in part, substantially further) removed from one another than this whole number, and in some cases even alongside one another.
The interleaving in a transport multiplexing method is frequently carried out in two steps. The various solutions for carrying out the puncturing/repetition have specific consequences when the puncturing is carried out downstream of the first interleaver as is provided for the UMTS system. It is necessary here to take particular notice of the fact that the performance could deteriorate when a block interleaver with a column exchange, such as the FS-MIL (FS Multistage Interleaver) used in UMTS, is used as interleaver in the up-link multiplexing method in conjunction with a rate matching algorithm. Downstream of the first interleaver, the bits assigned to a frame are further interleaved by a second interleaver that is described, for example, in TS 25.212 (see below for more accurate details), Chapter “4.2.11 2nd interleaving.” This second interleaver has no influence, however, on aspects of the puncturing/repetition and is therefore not taken further into account below; it is of no importance with regard to the present invention. Consequently, the above-named first interleaver is frequently also simply named interleaver in this document.
A block interleaver with column exchange functions as follows. First, the bits are written rowwise into a matrix. This matrix includes F columns, F being the number of frames (also frequently termed radio frames or columns below) over which the data of a data frame are distributed; see also TS 25.212 (see below for more accurate details) Chapter “4.2.5 1st interleaving.”
In the current version of the UMTS standard (3GPP TSG RAN WG1; Multiplexing and channel coding (FDD); TS 25.212 V2.3.0 (1999-10)) Chapter “4.2.7 Rate matching,” in particular section “4.2.7.1.2 Determination of parameters needed for calculating the rate matching pattern,” a method is represented that was presented in the article R1-99641 (Siemens; Properties of optimised puncturing scheme; TSG-RAN WG1#5, June 1-4, Cheju, Korea). This method distributes punctured bits as uniformly as possible and, in particular, avoids the case of the puncturing of bits situated close to one another. This is also achieved for the case of the application of puncturing using the (interframe) interleaver. The same method also can be applied for the case of repetition, which likewise leads to good results.
In the article R1-99641 mentioned, the following modifications were proposed to the rate matching method The rate matching was carried out using the puncturing/repetition pattern by applying a common pattern to all frames, the pattern being displaced in the case of the individual frames. Use was made for calculating the displacement of simple calculating rules that take account of the effect of the column exchange by the interleaver (for example, an FS-MIL)) (the term column exchange, sometimes also termed column randomizing, is used here instead of “row-by-row processing”).
Owing to the fact that the operation of column exchange is taken into account in the formulas, the same effect is achieved as if the rate matching were carried out upstream of the column exchange of the interleaver, although for practical reasons it must be carried out downstream thereof. This is achieved by virtue of the fact that account is taken of the column exchange rule, more precisely its inversion RF (and RF, respectively, or RF(k) and RF(k), respectively) in the formulas for calculating S (the displacement of the pattern per column or frame) or eoffset (a parameter that is used in the rate matching algorithm, presented further below, that is carried out per frame). Similar procedures can be used for puncturing and repetition, the present invention particularly dealing with the case of repetition. The carrying out, necessary owing to other prescriptions, of the rate matching downstream of the first interleaver has consequences, in this case, for the optimum generation of puncturing and repetition patterns.
The aim of a good repetition method is to distribute the repeated bits as uniformly as possible. The same also holds for a good puncturing method. The method presented in the abovementioned article R1-99641 operates as represented below (for the sake of simplicity, puncturing/repetition will not always be written below, but only one alternative; it is obvious that the argument also can be applied for the other alternative). The most uniform distribution can be achieved when each nth bit is repeated. However, if the repetition rate or n is not integral, the spacing must be varied; that is, sometimes the nth and sometimes the n+1th bit must be repeated. An attempt also can be made to apply this principle when the repetition is applied downstream of the first interleaver, although there is a further secondary condition in this case: the repeated bits must be distributed uniformly over all radio frames.
As an example, an interleaving interval of 80 ms and a repetition rate of 1:6 will be assumed in FIG. 4. The numbers printed in bold mark the bits to be repeated. If each 6th bit were repeated, only bits in the columns 0,2,4,6 but not in the columns 1,3,5,7 would be repeated, which leads to a nonuniform distribution of the repeated bits over the radio frames. In order to distribute the repetitions uniformly over all columns, the repetition interval is sometimes modified (in this case, once) in order to prevent always the same columns from being punctured. This is shown in FIG. 4.
The narrow horizontal arrows with thin outlines show a repetition spacing of 6, and the wide horizontal arrow with a thick outline shows a repetition spacing, differing therefrom, of 5, in order to avoid repeating the first column too early a second time. After each column has been repeated once, the repetition pattern can be displaced downward by 6 rows, in order to determine the next bits (beginning at 48) to be repeated, and so on. Clearly, this procedure is equivalent to puncturing each 6th bit in a column and displacing this puncturing pattern in different columns relative to one another.
The formulas or the calculating method are specified below, with the aid of the example of puncturing, for the optimized method that is defined in the abovementioned article R1-99641 and is best suited to the case of puncturing.
The number of bits per radio frame before the rate matching can be denoted by Nc, the number of the bits per radio frame after the rate matching by N1, the index or the position of a bit to be punctured/repeated in the first column (k=0) by mj, the frame number by k, and the number of frames over which the interleaving is carried out by F. It is essentially the case of Nc>N1, that is to say puncturing, that is considered. However, the formulas also can be applied for the case of repetition. Let the following first set of parameters hold in the example: Nc=20, N1=16, m1=4, m2=9, m3=14, M4=19, k=0, . . . 7, and F=8. The displacement of the puncturing pattern then can be determined with the aid of the following formulas. Here and in the context of the overall application, a commentary on the corresponding steps is given after the double dash “--”
--calculation of the mean puncturing spacing.
q:=(└Nc/(/Ni−Nc/)┘)mod F-- here, └ ┘ signifies rounding down and // the absolute value.
Q:=(└Nc/(/N1−Nc/)┘)div F
if q is even—treat special case.
then q=q−1cd(q, F)/F                --Here, led (q, F) denotes the greatest common divisor of q and F.        
--The greatest common divisor can be calculated easily by bit manipulations when F is a power of two.
--For the same reason, calculations with p can be carried out easily by binary fixed-point operations (or, alternatively, by integer arithmetic with the use of displacement operations.
endif
--calculation of S and T; S represents the displacement of the row mod F and T the absolute displacement value div F;
S therefore represents the displacement of the row with respect to q (that is to say mod F), and T the absolute displacement value with respect to Q (that is to say, div F).
For i=0 to F−1
S(RF(┌i*q┐ mod F))=(┌i*q┐ div F)--┌ ┘ signifying rounding up.
T((RF(┌i*q┘ mod F))=--RF(k) inverts the interleaver,
end for
In a real implementation, these formulas can be implemented as a reference table, as shown in FIG. 5. The table also includes the effect of the column exchange taken into account by RF(k). S can be calculated from T as a further implementation option.
It is then possible to calculate eoffset as follows:eoffset(k)=((2*S)+2*T*Q+1)*y+1)mod 2Nc 
With the aid of eoffset(k), e is then preloaded in the rate matching method for UMTS. This choice of eoffset obviously effects a displacement of the puncturing patterns of the columns relative to one another or relative to the column denoted by k=0 by the amount S+T*Q.
eoffset is sometimes also termed einit. The rate matching method for UMTS, which is applied inside a single frame, is described in TS25.212 (see above for more accurate details), section 4.2.7.4 “Rate matching pattern determination.” It describes a puncturing or repetition method based on an error control. This method is described here once more.
Before the rate matching, the bits may be denoted as follows:
xl,1, xl,2, xl,3, xl,4, . . . xi,N, in which case i denotes the number of the transport channel (TrCH number) and Nis the parameter that is defined in chapter 4.2.7.2 of TS 25.212.
The rate matching algorithm then operates as follows:
if puncturing is to be carried out,
e=eini--initial error between the current and desired puncturing rate.
m = 1-- Index for the currently treated bit.  do while m <= N   e = e − eminus-- match error value.   if e <= 0 then -- query as to whether bit number m is to be   punctured.    Puncture bit xi,m    e = e + eplus-- match error value.   end if   m = m + 1-- next bit. end doelse e = eini--Initial error between the current and desired puncturing rate. m = 1-- Index for the currently treated bit. do while m <= N   e = e − eminus-- Match error value.   do while e <= 0-- query as to whether bit number m  is to be repeated.   repeat bit Xi,m   e = e + eplus-- match error value. end do m = m + 1-- next bit. end doend if
If a bit is repeated, it is inserted immediately after the bit originally already present.
Described below is a simplified representation which simply results from the fact that the calculation of q and Q is not carried out separately for the remainder in the case of the division by F and the multiple of F, but in a combined fashion for both components. In the same way, S and T cannot be calculated separately for q and Q, but are likewise calculated in a combined fashion. The substitution q+F*Q→q and S+Q*T→S yields the following equivalent representation. Depending on the details of the implementation, one or other calculation method (or further methods likewise equivalent thereto) can be carried out more favorably.
--Calculation of the mean puncturing distance
q:=(└Nc/(|Ni−Nc|)┘)--└ ┘signifying rounding down and ∥ signifying absolute value.
if q is even--treat special case.
then q=q−1cd(q, F)/F--1cd (q, F) signifying the greatest common divisor of q and F.
--note that led can be calculated easily by bit manipulations, because F is a power of two.
--For the same reason, calculations with q can be carried out easily with the aid of binary fixed-point arithmetic (or integer arithmetic and a few shift operations). endif
--Calculation of S(k) of the displacement of column k.
for i=0 to F−1
S(RF(┌i*q┐ mod F))=(┌i*q┐ div F)--┌ ┐ signifying rounding up.
--RF(k) inverts the interleaver.
end for
It is then possible to calculate eoffset in the following way:
eoffset(k)=((2*S)*y+1)mod 2Nc 
With the aid of eoffset(k), e is then initialized in advance in the rate matching method.
Those skilled in the art know that the constant 1 used in this definition of eoffset also can be replaced by any other value desired if it is identical for all columns or frames. For reasons of simplified representation, this will not be examined explicitly below. Furthermore, the methods presented can be further modified or expanded, although the basic assumptions are retained.
If the puncturing rate is an odd-numbered fraction (that is to say with an odd denominator), such as 1:5 or 1:9, this known method produces the same perfect puncturing pattern that would be applied directly before interleaving by puncturing with the use of the rate matching method. In other cases, adjacent bits are never punctured; however, a distance between punctured bits can be greater than the others by up to 1cd(q,F)+1. This method also can be applied correspondingly to bit repetitions. Although the repetition of adjacent bits does not impair the performance of the error correction code so strongly as is the case when puncturing adjacent bits, it is nevertheless advantageous to distribute repeated bits as uniformly as possible.
The fundamental objective of this known method is to achieve a uniform spacing between the punctured bits in the original sequence, while taking account, however, of the constraint that the same number of bits are to be punctured in the various frames. This is achieved by virtue of the fact that the puncturing distance is reduced by 1 in specific cases. The method presented is optimum to the extent that it never reduces the distance by more than 1 and reduces it only as often as necessary. This yields the best possible puncturing pattern subject to the constraints mentioned above.
The following example shows the use of the first set of parameters (Nc=20, N1=16, m1=4, m2=9, m3=14, m4=19, k=0, . . . 7, and F=8), that is to say puncturing with 1:5 (FIG. 6). The optimized method obviously not only avoids the puncturing of adjacent bits, but moreover distributes punctured bits with the same spacing in the original sequence. In fact, the same characteristics are achieved as if the puncturing had been carried out directly after the coding and before the interleaving.
The aim now is to investigate the next case, that is to say puncturing with 1:8 (FIG. 7). Once again, the puncturing of adjacent bits is avoided. In this case, it is impossible to achieve uniformly spaced puncturing, because all the bits in an individual frame would be punctured, which is completely unacceptable. In this case, most of the distances between adjacent bits are 7 (only 1 less than in the case of an optimum distribution). In return, some distances are greater (every eighth).
However, it has emerged that the previously proposed solutions, that is to say the proposed puncturing pattern in the case of application as a repetition pattern, still is not always optimal in all cases. Starting therefrom, it is an object of the present invention to reduce the disadvantages of the prior art. In particular, it is an object of the present invention to specify a technical teaching that permits decoding of good quality in the receiver; particularly, in the case of the repetition of bits.